package me.huangxiang.data_structure_and_algorithm.algorithms.dynamic_programming;

import java.util.Random;

public class TriangleMaxPathSum {
    private static int[][] triangle = null;
    private static int[][] cache = null;
    public static void createTriangle(int lineNum){
        Random random = new Random();
        triangle = new int[lineNum][lineNum];
        for (int i = 0; i < lineNum; i++){
            for (int j = 0; j <= i; j++){
                triangle[i][j] = randomNumWithinTen(random);
            }
        }

        // 打印出数字三角形
        for (int i = 0; i < lineNum; i++){
            for (int j = 0; j <=i; j++){
                System.out.print(triangle[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

    private static int randomNumWithinTen(Random random){

        int value = 0;
        do {
            value = random.nextInt(20);
        } while (value == 0);
        return value;
    }

    public static void main(String[] args) {
        int lineNum = 45;
        createTriangle(lineNum);
//        int sum = maxSum(0, 0);
//        System.out.println(sum);
        cache = new int[lineNum][lineNum];
        int sumMemmoi = maxSumMemmoi(0, 0);
        System.out.println(sumMemmoi);

        int sumUsingIteration = maxSumUsingIteration(lineNum);
        System.out.println(sumUsingIteration);
    }

    // 通过话递归调用图可以发现，这种递归方式的算法时间是O(2^n)
    public static int maxSum(int i, int j){
        if (i == triangle.length - 1){
            return triangle[i][j];
        }else {
            return Math.max(maxSum(i + 1, j), maxSum(i + 1, j + 1)) + triangle[i][j];
        }
    }

    // 使用一个缓存用来存储已经算过的maxSum
    public static int maxSumMemmoi(int i, int j){
        if (i == triangle.length - 1){
            return triangle[i][j];
        }else {
            if (cache[i][j] != 0){
                return cache[i][j];
            }else {
                int tmp = Math.max(maxSumMemmoi(i + 1, j), maxSumMemmoi(i + 1, j + 1)) + triangle[i][j];
                cache[i][j] = tmp;
                return tmp;
            }
        }
    }

    // 自底而上不断迭代从而得到问题的解
    public static int maxSumUsingIteration(int lineNum){
        int maxSum[][] = new int[lineNum][lineNum];
        for (int i = 0; i < lineNum; i++){
            maxSum[lineNum - 1][i] = triangle[lineNum - 1][i];
        }

        for (int i = lineNum - 2; i >= 0; i--){
            for (int j = 0; j <= i; j++){
                maxSum[i][j] = Math.max(maxSum[i + 1][j], maxSum[i + 1][j + 1]) + triangle[i][j];
            }
        }

        return maxSum[0][0];
    }
}
